#include<iostream>
#include<map>
#include<algorithm>
#define sc scanf
#define pr printf
using namespace std;
const int INF=1e9;
map<string,int>m;
typedef struct City{
	string name;
	int next[210];
	int goldcoin[210];
	int tail,score;
}city;
city c[210];
int book[210];
int cnt,maxScore;
int minCoins=INF,needMove=INF;
typedef struct St{
	string S;
}route;
route r[210];
int rtail;
void DFS(int now,int coins,int scores,int step){
	if(c[now].name=="MLB"){
		if(minCoins>coins){
			if(cnt)	cnt=0;
			else cnt++;
			minCoins=min(minCoins,coins);
			maxScore=max(maxScore,scores);
			needMove=min(needMove,step);
		}
		else if(minCoins==coins){
			cnt++;
			minCoins=min(minCoins,coins);
			maxScore=max(maxScore,scores);
			needMove=min(needMove,step);
		}
		
		return;
	}
	int j;
	for(j=0;j<c[now].tail;j++){
		if(!book[c[now].next[j]]){
			book[c[now].next[j]]=1;
//				r[rtail++].S=c[ c[now].next[j] ].name;
				DFS(c[now].next[j],coins+c[now].goldcoin[j],
					scores+c[ c[now].next[j] ].score , step+1);
			book[c[now].next[j]]=0;
		}
	}
	return;
}
void find_route(int now,int coins,int scores,int step){
	if(c[now].name=="MLB"&&scores==maxScore){
		cout<<c[0].name<<"->";
		for(int i=0;i<rtail;i++){
			cout<<r[i].S;
			if(i!=rtail-1)
				cout<<"->";
		}
		cout<<endl;
		return;
	}
	int j;
	for(j=0;j<c[now].tail;j++){
		if(!book[c[now].next[j]]){
			book[c[now].next[j]]=1;
			r[rtail++].S=c[ c[now].next[j] ].name;
				find_route(c[now].next[j],coins+c[now].goldcoin[j],
					scores+c[ c[now].next[j] ].score , step+1);
			r[rtail--].S="xxx";
			book[c[now].next[j]]=0;
		}
	}
	return;
}
int main()
{
	string temp1,temp2;
	int n,k,i,coin,p1,p2;
	cin>>n>>k>>c[0].name;
	for(i=1;i<n;i++){
		cin>>c[i].name>>c[i].score;
		m[ c[i].name ] = i;
	}
	for(i=0;i<k;i++){
		cin>>temp1>>temp2>>coin;
		p1=m[temp1];
		p2=m[temp2];
		c[ p1 ].next[ c[p1].tail ] = p2;
		c[ p1 ].goldcoin[c[p1].tail++] = coin;
		c[ p2 ].next[ c[p2].tail ] = p1;
		c[ p2 ].goldcoin[c[p2].tail++] = coin;
	}
	book[0]=1;
	DFS(0,0,0,0);
	cout<<cnt<<" "
	<<minCoins<<" "
	<<maxScore<<" "<<needMove<<endl;
	find_route(0,0,0,0);
	return 0;
}
